1. Technical Field
The present invention relates generally to the automated layout of integrated circuits. In particular, the present invention is directed toward automatic generation of optimized wire routing in very large scale integration (VLSI) circuits.
2. Description of Related Art
In recent years, it has become commonplace for integrated circuit designers to build an integrated circuit layout from libraries of reusable high-level modules, sometimes referred to as “macro blocks.” Proprietary macro blocks are often referred to as “intellectual property blocks” (“IP blocks”), to emphasize their relatively intangible, yet proprietary nature. Computerized integrated circuit design tools may be used to store, retrieve, and combine macro blocks into complete integrated circuits. This design philosophy of combining reusable macro blocks to produce a complex integrated circuit is known as “system-on-a-chip” (SoC) design. Designing a “system-on-a-chip” involves designing the interconnections between macro blocks. Despite the apparent simplicity of SoC design, this is often not a trivial task. The reason for this is that the connections themselves are physical components (i.e., wires) with non-ideal properties. Like all electrical conductors, integrated circuit connections suffer from delay and signal loss due to physical properties such as resistance, capacitance, and relativistic limitations on the speed at which electrons are able to travel. In order to ensure that all components in an integrated circuit are properly synchronized to work properly, it is important to take these factors into account when designing interconnections between macro blocks to minimize signal loss and to allow operation within acceptable timing specifications.
Buffer insertion is now widely recognized as a key technology for improving VLSI (Very Large Scale Integration) interconnect performance. For a buffer insertion technique to be effective, however, it must be fully aware of its surrounding blockage constraints while also being efficient enough to quickly process thousands of nets. In the buffer insertion literature, van Ginneken's dynamic programming based algorithm has established itself as a classic in the field. Van Ginneken's algorithm is described in L. P. P. van Ginneken, “Buffer placement in distributed RC-tree networks for minimal Elmore delay,” Proceedings of the IEEE International Symposium on Circuits and Systems, pp. 865–868, 1990, which is hereby incorporated by reference. Van Ginneken's algorithm assumes a Steiner tree routing topology and inserts buffers into the Steiner tree so as to minimize Elmore delay. The Elmore delay metric is described in R. Gupta, B. Tutuianu, and L. T. Pileggi, “The Elmore Delay as a Bound for RC Tree with Generalized Input Signals,” IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, vol. 16, no. 1, pp. 95–104 (January 1997), which is hereby incorporated by reference.
A Steiner tree is defined as follows: If, in a weighted graph, a subset of the vertices are designated as “terminals,” a Steiner tree is a minimum-weight connected subgraph which includes all of the “terminals.” Thus, for example, a minimum spanning tree of a graph is a special case of a Steiner tree in which all of the vertices in the graph are selected as terminals. A Steiner node is an interior node (i.e., not a root or leaf node) in a Steiner tree.
In J. Lillis, C. K. Cheng, and T. Y. Lin. “Optimal wire sizing and buffer insertion for low and a generalized delay model,” IEEE Journal of Solid-State Circuits, 31(3): 437–447, March 1996, Lillis et al. extended van Ginneken's algorithm by using a buffer library with inverting and non-inverting buffers, while also considering power consumptions.
One weakness of the van Ginneken approach is that it requires a fixed Steiner tree topology has to be provided in advance, which makes the final buffer solution quality dependent on the input Steiner tree. Even though it is optimal for a given topology, the van Ginneken algorithm will yield poor solutions when fed a poor topology. To overcome this problem, several works have proposed simultaneously constructing a Steiner tree while performing buffer insertion. J. Lillis, C. K. Cheng, and T. Y. Lin, “Simultaneous routing and buffer insertion for high performance interconnect,” Proceedings of the Great Lake Symposium on VLSI, pages 148–153, 1996. describes the “buffered P-Tree” algorithm, which integrates buffer insertion into the P-Tree Steiner tree algorithm.
Buffered P-Tree generally yields high quality solution, but its time complexity is also high because candidate solutions are explored on almost every node in the Hanan grid. In the recently reported S-Tree algorithm, alternative abstract topologies for a given Steiner tree are explored to promote solutions that are better at dealing with sink criticalities. S-Tree is described in M. Hrkic and J. Lillis, “S-tree: A technique for buffered routing tree synthesis,” Proceedings of the ACM/IEEE Design Automation Conference, pages 578–583, 2002. The S-Tree technique is integrated with P-Tree as SP-Tree algorithm in M. Hrkic and J. Lillis, “Buffer tree synthesis with consideration of temporal locality, sink polarity requirements, solution cost and blockages.” Proceedings of the ACM International Symposium on Physical Design, pages 98–103, 2002.
A different approach to remedying this weakness of van Ginneken's algorithm is described in C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, and A. J. Sullivan, “Buffered Steiner trees for difficult instances,” IEEE Transactions on Computer-Aided Design, 21(1): 3–14, January 2002, which is hereby incorporated by reference. Alpert et al. construct a “buffer-aware” Steiner tree, using an algorithm called C-Tree, for van Ginneken's algorithm. Despite being a two-stage sequential method, C-Tree yields solutions comparable in quality to simultaneous methods, while consuming significantly less CPU time.
Recent trends toward hierarchical (or semi-hierarchical) chip design and system-on-chip design force certain regions of a chip to be occupied by large building blocks or IP cores so that buffer insertion is not permitted. These constraints on buffer locations can severely hamper solution quality, and these effects need be considered. Thus buffer blockages are considered in the “buffered path” class of algorithms. Several such algorithms are described in H. Zhou, D. F. Wong, I-M. Liu, and A. Aziz. “Simultaneous routing and buffer insertion with restrictions on buffer locations,” Proceedings of the ACM/IEEE Design Automation Conference, pages 96–99, 1999; A. Jagannathan, S.-W. Hur, and J. Lillis, “A fast algorithm for context-aware buffer insertion,” Proceedings of the ACM/IEEE Design Automation Conference, pages 368–373, 2000; and M. Lai and D. F. Wong, “Maze routing with buffer insertion and wiresizing,” Proceedings of the ACM/IEEE Design Automation Conference, pages 374–378, 2000. Though optimal, the buffered path algorithms are only applicable to two-pin nets. Works that handle restrictions on buffer locations while performing simultaneous Steiner tree construction and buffer insertion are proposed in J. Cong and X. Yuan, “Routing tree construction under fixed buffer locations,” Proceedings of the ACM/IEEE Design Automation Conference, pages 379–384, 2000 and X. Tang, R. Tian, H. Xiang, and D. F. Wong, “A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints,” Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pages 49–56, 2001. Like buffered P-Tree, these approaches can provide high quality solutions, though at runtimes that can be too high for practical use in a physical synthesis system.
In C. J. Alpert, G. Gandham, J. Hu, J. L. Neves, S. T. Quay, and S. S. Sapatnekar, “A Steiner tree construction for buffers, blockages, and bays,” IEEE Transactions on Computer-Aided Design, 20(4): 556–562, April 2001, which is hereby incorporated by reference, a Steiner tree is rerouted to avoid buffer blockages before conducting buffer insertion. This sequential approach is fast, but sometimes results in poor solutions, due to unnecessary wiring detours. An adaptive tree adjustment technique for obtaining a good solution more efficiently is provided in a commonly assigned, co-pending U.S. patent application entitled “BUFFER INSERTION WITH ADAPTIVE BLOCKAGE AVOIDANCE,” Ser. No. 10/324,732, filed Dec. 18, 2002, which is hereby incorporated by reference.
The Importance of Porosity
In tradition design processes, buffer insertion is applied after block placement to optimize interconnect timing. As interconnect effects become increasingly severe, however, buffer insertion needs to be addressed earlier in the design process to help logic optimization and placement algorithms with interconnect estimation and to reserve buffering resources. The sheer number of nets that may require buffering suggests that resources need to be allocated intelligently. For example, large blocks placed close together create narrow alleys that become likely locations for a buffer placement algorithm to insert buffers, since such alleys are the only locations in which buffers can be inserted for routes that cross over these blocks.
Competition for resources for these routes can be very fierce, though. Inserting buffers for less critical nets can eliminate space needed for more critical nets that may require gate sizing or other logic transforms. Further, though no blockages lie in the alleys, the alleys could already be packed with logic and no feasible space for a buffer might exist. If a buffer insertion algorithm cannot recognize this scenario, then inserting a buffer into such a space will cause a non-realizable solution. To make the solution legal, the buffer or may be forced to move to an awkward, sub-optimal position that fails to meet timing requirements. Hence, whenever possible a buffer insertion algorithm should avoid more densely populated regions unless absolutely critical.
In this document, an algorithm that avoids inserting buffers into dense regions is referred to as being “porosity-aware.” “Porosity,” for the purposes of this document, refers to the degree to which a given region is not dense. Thus, “porosity” may be thought of as the opposite of “density.” A number of different measures for porosity may be defined and used within the context of an embodiment of the present invention.
For example, FIG. 1A shows a 2-pin net 100 which is routed through a dense region or “hot spot” 102, and FIG. 1B shows net 100 routed differently to avoid dense region 102. Both solutions have the same wirelength and timing characteristics. FIGS. 1C and 1D show another example for a multi-pin net 106 where a Steiner point 108 needs to be moved outside of a dense region 110 to yield an improved buffer insertion result.
The literature contains no buffering approach that addresses these issues. Note that several algorithms (such as S-Tree and SP-Tree) could be used to address porosity constraints, since they can be run on arbitrary grid graphs. However, the extensions to such algorithms that are necessary to make such algorithms porosity-aware are hardly straightforward. One has to carefully consider factors such as (but not limited to) the weighting scheme for edges in the grid graph, how to sparsify the graph to give reasonable runtimes, the appropriate cost functions, and the like. Further, any simultaneous approach is likely to require too much runtime to be of practical use for physical synthesis. Thus, a need exists for an efficient and porosity-aware approach to constructing buffered Steiner trees that is straightforward to implement.